package com.imooc.distributedemo.resume.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 一些算法测验
 */
public class SolutionTech {

    public static void main(String[] args) {
        int[] S = {-1, 0 ,1 ,2 ,-1 ,-4};
        List<List<Integer>> result = threeSum((S));
        System.out.println(result);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public static List<List<Integer>> threeSum (int[] num) {
        // write code here
        if(null==num || num.length==0){
            return null;
        }
        Arrays.sort(num);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < num.length-2; i++) {
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            int left = i+1;
            int right = num.length-1;
            while (left<right){
                int sum = num[i]+num[left]+num[right];
                if(sum==0){
                    result.add(Arrays.asList(num[i],num[left],num   [right]));
                    left++;
                    right--;
                    while (left<right&&num[left]==num[left-1]){
                        left++;
                    }
                    while(left<right && num[right]==num[right+1]){
                        right--;
                    }
                }else if(sum<0){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return result;
    }
}
